#ifndef MERGESORT_H_
#define MERGESORT_H_
int inversions = 0;
void merge(int *a, int b, int m, int e) {
	int *left = new int[m - b];
	for (int i = b; i < m; i++)
		left[i - b] = a[i];
	int i = b, j = m;
	int p = b;
	while (i < m || j < e) {
		if (i < m && (left[i - b] <= a[j] || j >= e))
			a[p++] = left[i++ - b];
		if (j < e && (left[i - b] > a[j] || i >= m)) {
			inversions += m - i;
			a[p++] = a[j++];
		}
	}
	delete[] left;
}

void mergeSort(int *a, int begin, int end) {
	if (end - begin <= 1) {
		return;
	}
	int middle = begin + ((end - begin) >> 1);
	mergeSort(a, begin, middle);
	mergeSort(a, middle, end);
	merge(a, begin, middle, end);
}
#endif